//
#include "priorityqueue.h"

PQElement::PQElement()
{
	object=0L;
	key=0;
}

PQElement::PQElement(void* obj, int inputKey)
{
	object=obj;
	key=inputKey;
}

PQElement::~PQElement()
{

}

PriorityQueue::PriorityQueue()
{
	queue=0L;
	position=0L;
	numMembers=0;
	totalSize=0;
}

PriorityQueue::PriorityQueue(int size)
{
	queue=new PQElement[size+1];
	position = new int[size+1];
	totalSize=size;
	numMembers=0;
}
PriorityQueue::~PriorityQueue()
{
	

}
void PriorityQueue::Add(void* addition, int inputKey)
{
	numMembers++;
	position[numMembers]=numMembers;
	queue[numMembers].object=addition;
	queue[numMembers].key=inputKey;
	queue[numMembers].originalPosition=numMembers;
	HeapifyUp(numMembers);
}

void PriorityQueue::Delete(int pos)
{
	if (numMembers>0)
	{
		position[(queue[pos]).originalPosition]=0;
		queue[pos]=queue[numMembers];
		position[(queue[pos]).originalPosition]=pos;
		numMembers--;
		PQElement null;
		queue[numMembers+1]=null;
		if ((queue[pos/2]).key > (queue[pos]).key)
			HeapifyUp(pos);
		else
			HeapifyDown(pos);
	}
}

void* PriorityQueue::Extract_Min()
{
	if (numMembers>0)
	{
		PQElement temp=queue[1];
		Delete(1);
		return temp.object;
	}
	else
		return 0L;
}

void PriorityQueue::Change_Key(int orgPos, int newKey)
{
	if (numMembers>0)
	{
		(queue[position[orgPos]]).key=newKey;
		if ((queue[position[orgPos]/2]).key > (queue[position[orgPos]]).key)
			HeapifyUp(position[orgPos]);
		else
			HeapifyDown(position[orgPos]);
	}
}

void PriorityQueue::HeapifyUp(int initPos)
{
	if (initPos>1)
	{
		if ((queue[initPos/2]).key > (queue[initPos]).key)
		{
			PQElement temp = (queue[initPos/2]);
			queue[initPos/2]=queue[initPos];
			queue[initPos]=temp;
			position[(queue[initPos]).originalPosition]=initPos;
			position[(queue[initPos/2]).originalPosition]=initPos/2;
			HeapifyUp(initPos/2);
		}
	}
}

void PriorityQueue::HeapifyDown(int initPos)
{
	int minIndex=0;
	if (!(2*initPos>numMembers))
	{
		if(2*initPos<numMembers)
		{
			if ((queue[2*initPos]).key<(queue[2*initPos+1]).key)
				minIndex=2*initPos;
			else
				minIndex=2*initPos+1;
		}
		else
			minIndex=2*initPos;

		if ((queue[initPos]).key>(queue[minIndex]).key)
		{
			PQElement temp = (queue[initPos]);
			queue[initPos]=queue[minIndex];
			queue[minIndex]=temp;
			position[(queue[minIndex]).originalPosition]=minIndex;
			position[(queue[initPos]).originalPosition]=initPos;
			HeapifyDown(minIndex);
		}
	}
}
